1. Field of the Invention
The present invention relates to a pattern recognition method capable of analyzing a new pattern based on patterns learned beforehand. According to a typical example, images of a target object are captured and used as patterns for the pattern recognition. For example, the pattern recognition is employable to estimate target information (e.g., name, type, and three-dimensional position and orientation of the target object). In this case, the target object to be processed in the pattern recognition can be an arbitrary object, which is, for example, a human, an animal, an internal organ, an automotive vehicle, a camera, a printer, a semiconductor substrate, or any other object. Further, as another example, measurement values of a target physical phenomenon can be used as patterns that can be processed in the pattern recognition.
2. Description of the Related Art
The machine learning is generally known as a conventional technique capable of analyzing a new pattern based on learning patterns. Especially, classification trees and decision trees are well known as representative elements used in the pattern recognition method and widely used in many systems (see Leo Breiman, Jerome Friedman, Charles J. Stone, and R. A. Olshen, “Classification and Regression Trees”, Chapman & Hall/CRC (1984) (hereinafter, referred to as Literature 1). The above-mentioned conventional method is characterized in that a pattern can be quickly analyzed with reference to a tree structure and the processing speed is superior to that of a conventional computer whose capabilities are insufficient or poor.
In the following description, regarding pattern recognition problems as being equivalent to pattern discrimination problems is meaningful. In this case, the type of each pattern to be discriminated is referred to as “class” and therefore, the technical term “class” is intentionally used in the following description.
On the other hand, the conventional classification trees and decision trees discussed in Literature 1 are disadvantageous in that the recognition performances are not so excellent.
As a conventional technique capable of solving the disadvantages of the classification trees and decision trees, a method discussed, for example, in U.S. Pat. No. 6,009,199 uses an assembly (ensemble) of classification trees. More specifically, the method discussed in U.S. Pat. No. 6,009,199 includes a process of generating a total of L classification trees, in which L is an integer equal to or greater than two and is generally in a range from 10 to 100. Then the method further includes a process of performing recognition processing using all of the generated classification trees in such a way as to realize higher performances.
The above-described assembly (ensemble) of classification trees is applicable to the computer vision as discussed in Vincent Lepetit and Pascal Fua, “Keypoint Recognition Using Randomized Trees”, IEEE Transactions on Pattern Analysis and Machine Intelligence (2006) pp. 1465 to pp. 1479 (hereinafter, referred to as Literature 2). In Literature 2, a target to be processed is an image of 32 pixels*32 pixels and classification trees are successively generated based on its luminance values. More specifically, at each node of a classification tree, two points are randomly selected from an image of 32 pixels*32 pixels. Then, separation of the branch is determined based on a comparison between luminance values of the selected points. According to the description in Literature 2, the processing speed is very high and the recognition accuracy is sufficient.
However, for example, the target to be recognized may be a piece of product in a huge accumulation of products or a human in the crowd. In this case, the background is variable so greatly that the method discussed in Literature 2 cannot be directly used, because the luminance value of a portion serving as the background is greatly different from that of a target image to be learned in an unknown image. More specifically, when luminance values of two selected points are compared at each node of a classification tree, a compared luminance value may not be relevant to that of the target object. Thus, the conventional pattern recognition using classification trees may provide a result not so reliable.
On the other hand, the matching method discussed in Japanese Patent No. 3166905, which is based on correlation calculation using a mask image and applied to only a target object portion, has been conventionally used to solve problems in object recognition within background clutter scenes. However, if a large-scale problem occurs in object recognition, a conventional correlation calculation based on the matching method, which is discussed, for example, in Japanese Patent No. 3166905, cannot be employed because a very long time is required to accomplish calculation. More specifically, when the target to be recognized is a product component, the number of orientations (including rotations within the same plane) to be discriminated may rise up to 10,000 or more. In this case, the processing according to the method discussed in Japanese Patent No. 3166905 cannot be accomplished within a practical processing time.